package leetcode.D100.T42;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-11 20:30:27 星期五
 */

class Solution {
    // 一刷
    /*public int trap(int[] height) {
        int[] leftMax = new int[height.length], rightMax = new int[height.length];
        int result = 0;
        for(int i=1; i<height.length; ++i) {
            leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
        }
        for(int i=height.length-2; i>=0; --i) {
            rightMax[i] = Math.max(rightMax[i+1], height[i+1]);
        }
        for(int i=1; i<height.length-1; ++i) {
            int border = Math.min(leftMax[i], rightMax[i]);
            if (border > height[i]) {
                result += (border-height[i]);
            }
        }
        return result;
    }*/

    // 二刷,双指针

    /**
     * 思路:
     *  在方法一中,空间复杂度为O(n),但这是可以进一步降低的
     *  只需要记录左边界(左边最大)和右边界(右边最大)即可,并不用两个数组来记录
     *  并且双指针在每次移动时,优先移动边界较小的一边,这是因为决定某一列能装多少水,关键看左右边界中较小值
     */
    /*public int trap(int[] height) {
        int result = 0, left = 1, right = height.length-2;
        int leftBorder = height[0], rightBorder = height[height.length-1];
        while (left <= right) {
            if (leftBorder <= rightBorder) {
                if (leftBorder > height[left])
                    result += (leftBorder - height[left]);
                leftBorder = Math.max(leftBorder, height[left]);
                left++;
            } else {
                if (rightBorder > height[right])
                    result += (rightBorder - height[right]);
                rightBorder = Math.max(rightBorder, height[right]);
                right--;
            }
        }
        return result;
    }*/

    public int trap(int[] height) {
        int left = 1, right = height.length - 2, res = 0;
        int leftBorder = height[0], rightBorder = height[height.length-1];
        while (left <= right) {
            if (leftBorder <= rightBorder) {
                if (leftBorder > height[left])
                    res += (leftBorder - height[left]);
                leftBorder = Math.max(leftBorder, height[left++]);
            } else {
                if (rightBorder > height[right])
                    res += (rightBorder - height[right]);
                rightBorder = Math.max(rightBorder, height[right--]);
            }
        }
        return res;
    }
}